Strom (graf)

V teorii grafů se jako strom označuje graf, který je souvislý a neobsahuje žádnou kružnici. Lze jej ovšem definovat i dalšími způsoby:

Následující podmínky pro neorientovaný graf G jsou ekvivalentní:

1. G je strom.
2. Každé dva vrcholy z G jsou spojeny právě jednou cestou (jednoznačnost cesty).
3. G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost).
4. G neobsahuje kružnici, ale po přidání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) .
5. G je souvislý a ${\displaystyle \left|V\right|=\left|E\right|+1}$, kde V je množina vrcholů a E množina hran grafu G.

Stromy mohou být:

• neorientované
• orientované (kořenové)